/*
 * Copyright (C) 2006  Nicolas Normand
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

#ifndef ALGO_STD_DIJKSTRA_H_
#define ALGO_STD_DIJKSTRA_H_

#include "graph.h"

namespace algorithm
{
	template <typename A, typename W>
	class Edge2Weight
	{
		public:
		W operator()(A& a)
		{
			return (W)a;
		}
	};

	template <typename V, typename A, typename Weight, typename e2wConvertor = Edge2Weight<A, Weight> >
	class std_dijkstra
	{
		public:
		Weight Infiny;

		typedef struct
		{
			int predecessor;
			Weight lenght;
		} dijkstra_res;

		private:
		virtual int pop_min(std::list<int>& l, std::vector<Weight>& d, int n)
		{
			Weight i = this->Infiny;
			int s = -1;
			std::list<int>::iterator it = l.begin();
			std::list<int>::iterator it2;
			e2wConvertor e2w;
			while (it != l.end())
			{
				if (( e2w(d[*it]) < i) || ( e2w(d[*it]) == i && i == this->Infiny))
				{
					i = e2w(d[*it]);
					s = *it;
					it2 = it;
				}
				it++;
			}
			l.erase(it2);
			return s;
		}
	
		public:
		std_dijkstra(Weight infiny) { Infiny = infiny; }
		virtual ~std_dijkstra() {}

		virtual std::vector<dijkstra_res> operator()(graph::basic<V, A>& g, int s)
		{
			std::list<int> S;
			std::list<int> S_;
			std::vector<Weight> d; // Distance
			std::vector<int> p;    // Predecessor
			int n = (signed int)g.vertexes().size();

			// Initialisation
			for (int i=0; i<n; i++)
			{
				d.push_back(this->Infiny);
				p.push_back(-1);
				S_.push_back(i);
			}
			d[s] = 0;
			e2wConvertor e2w;
			
			while (S.size() != (unsigned int)n)
			{
				std::list<int> succ;
				std::list<int>::iterator it;
				int i;
				
				i = pop_min(S_, d, n);
				S.push_back(i);
				
				succ = g.successors(i);
				it = succ.begin();
				while (it != succ.end())
				{
					if (d[i] != this->Infiny && d[*it] > d[i] + e2w(g.edge(std::pair<int, int>(i, *it))))
					{
						d[*it] = d[i] + e2w(g.edge(std::pair<int, int>(i, *it))); // TODO: check for overflow
						p[*it] = i;
					}
					it++;
				}
			}

			std::vector< dijkstra_res > res;
			for (int i=0; i<n ; i++)
			{
				dijkstra_res r;
				r.predecessor = p[i];
				r.lenght = d[i];
				res.push_back(r);
			}

			return res;
		}

	}; // End of: class


	// TODO: dijkstra with binary heap
	
} // End of: namespace

#endif

